A sequence of pictures can occupy a vast amount of storage space and require very high transmission bandwidth when represented in an uncompressed digital form. Point to point digital video communication became practicable several years ago following advances in computer networks and signal compression technology.
The standardization effort for digital video compression was initiated in approximately 1988. Currently, the Moving Picture Experts Group (MPEG) committee under ISO/IEC has completed both the MPEG-1 and the MPEG-2 standards; the MPEG-4 standard has also been completed, but new proposals are still being accepted. In addition, CCITT developed a series of recommendations—H.261, H.263 and H.263+—that focus on low bit rate applications. All of these attempts at standardization utilize a two-step procedure to compress a video sequence. The first step uses a motion estimation and compensation algorithm to create a predicted video frame for the current video frame using the previous video frame, wherein the difference between the current video frame and the predicted video frame is computed and is called the motion residual picture (MRP). The second step in the standard procedure is to code the MRP using the Discrete Cosine Transform (DCT). Such DCT-based systems do not perform well in all circumstances. At the low bit rates needed for personal video communication, DCT-based systems cause noticeable distortion and visible block artifacts. For high visual quality applications, such as DVD, the compression ratio achieved can be quite low.
Motion residual pictures can be coded using other transform-based techniques. For example, discrete wavelet transforms (DWT) and overcomplete basis transforms can also be used. Zakhor and Neff presented a motion residual coding system in U.S. Pat. No. 5,699,121 based on an overcomplete basis transform algorithm called matching pursuit. This was first proposed by Mallat and Zhang in IEEE Transaction in Signal Processing, vol. 41, No. 12, December 1993. Zakhor and Neff's video coder improves both the visual quality and the PNSR over standard DCT-based video coders. However, their system is very slow and the compression performance is not optimized due to an ad-hoc design for matched basis position coding and quantization of the transform coefficients. Therefore there is a need for a new overcomplete transform based video coding technique that can provide both speed and efficiency.
This background information is provided for the purpose of making known information believed by the applicant to be of possible relevance to the present invention. No admission is necessarily intended, nor should be construed, that any of the preceding information constitutes prior art against the present invention.